šŸ“Š Longest Increasing Subsequence (LIS)

Discover the longest strictly increasing subsequence in an array

šŸ‘©ā€šŸ’» Exploring Increasing Sequences

šŸŽÆ The Mission:

Find the length of the longest strictly increasing subsequence in an integer array to understand sequence patterns.

šŸ“‹ Requirements:

  • Compute the length of the longest strictly increasing subsequence
  • Handle arrays of length 1 to 100
  • Elements range from -10^4 to 10^4
  • Output the length as a single integer

Input/Output Specifications

  • Input: Integer n (array length), followed by n space-separated integers
  • Output: Length of the longest strictly increasing subsequence

Example: nums = [7, 7, 7, 7, 7, 7, 7]

Array:

7
7
7
7
7
7
7

LIS Length: 1 (e.g., [7])

Example: nums = [0, 1, 0, 3, 2, 3]

0
1
0
2
3
3

LIS Length: 4 (e.g., [0, 1, 2, 3])

āš” LIS Explained

How LIS Works

  1. Dynamic Programming: Use a DP array where dp[i] is the length of the LIS ending at index i
  2. Compare Elements: For each element, check previous elements to extend the subsequence
  3. Track Maximum: Keep track of the maximum LIS length

DP Table Example (nums = [0, 1, 0, 3, 2, 3])

Index012345
Element010323
DP Value121334

LIS Length: 4 (e.g., [0, 1, 2, 3])

Time Complexity

O(nĀ²)

For nested loops over n elements

Space Complexity

O(n)

For DP array

Why LIS?

  • āœ… Finds longest increasing patterns in sequences
  • āœ… Useful in scheduling, bioinformatics, and more
  • āœ… Simple DP approach is intuitive
  • āŒ Quadratic time complexity for large arrays

šŸ” Step-by-Step LIS Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input array
2. Build DP table
3. Display result

Current Array:

DP Table:

šŸŽ® Practice LIS

Enter array and click "Find LIS"

Test Cases

Example 1: nums = [7, 7, 7, 7, 7, 7, 7] ā†’ LIS Length: 1

Example 2: nums = [0, 1, 0, 3, 2, 3] ā†’ LIS Length: 4

šŸ“Š Algorithm Analysis

LIS Process

  1. Initialize DP: Set dp[i] = 1 for all indices
  2. Compute DP: For each index i, check previous indices j where nums[j] < nums[i]
  3. Update Maximum: Track the maximum dp[i] as the LIS length

Time Complexity

O(nĀ²)

For nested loops over n elements

Space Complexity

O(n)

For DP array

Key Points

  • Dynamic Programming: Efficiently computes LIS length
  • Strictly Increasing: Ensures nums[i] > nums[j]
  • Applications: Scheduling, sequence analysis
  • Limitation: Quadratic time for large inputs